\chapter{最优种子节点个数}

\section{引言}

在第\ref{sec1.3.4}节中我们提到，现有影响最大化算法都将种子节点个数$k$作为算法的输入，且针对影响最大化算法的研究都默认使用$k=50$来进行实验。在做现实社交网络的影响最大化分析时，用户选择$k=50$也许并不合适。如在线营销应用中，$k$越大意味着需要付出的预算越多。假如选择20个种子节点时信息的传播范围就能达到选择50个种子节点时相近的效果，那么对于额外30个节点的付出就等于是浪费预算。事实上，影响最大化问题目标就是为了节约预算，否则我们可以将产品送给每一个人，即选择$k=|V|$，就可以使影响传播给每一个人。

因此，如何选择合适的种子节点集合大小$k$是一个非常重要且有实际意义的问题。我们希望选择一个合适大小的$k$，使得在影响范围足够大的前提下预算浪费最少，我们称这个$k$为最优种子节点个数。

在本章中，我们首先给出最优种子节点个数的定义。接着，我们通过在大规模人工生成的模拟网络和现实社交网络中的实验，给出最优种子节点个数与信息传播模型中传播概率的关系。

\section{最优种子节点个数定义}

根据经济学原理中的边际收益\cite{landsburg_price_2010}，我们给出最优种子节点的形式化定义。

令$S^*$表示当前的种子节点集合，$RanCas(S^*)$表示$S^*$能激活的节点集合。则在$S^*$中加入新的种子节点$u$后，$u$能新激活的节点集合为$RanCas(S^* \cup \{u\}) - RanCas(S^*)$，该集合的大小为$MR_u = |RanCas(S^* \cup \{u\}) - RanCas(S^*)|$。可以认为，$MR_u$为在当前种子节点集合加入节点$u$后，节点$u$能获得影响范围的边际收益。接着我们定义节点$u$能获得影响范围的边际收益率为:
$$RMR_u=\frac{|RanCas(S^* \cup \{u\}) - RanCas(S^*)|}{|RanCas(S*)|}$$

$RMR_u$表示在加入节点$u$后，$u$影响范围的边际收益与当前总影响范围的比值。当$RMR_u$的值小于一个很小的阈值$\theta$时，我们认为加入节点$u$后影响范围的收益对于当前种子节点集合的影响范围而言已经微不足道。也就是说为$u$付出的预算带来的效益微乎其微，因此我们不再继续选择节点$u$作为种子节点。此外，由于不同应用中网络规模不同，影响范围的规模也不尽相同，因此为了消除网络不同造成的影响，我们选择边际收益率而不是边际收益作为指标。当$u$第一次满足$RMR_u<\theta$时，由于新加入的节点传播范围可忽略不计，说明当前种子节点集合的传播范围已经足够大；由于是第一次满足，说明预算浪费最少。

因此，我们定义最优种子节点集合为：满足对于任何的$v \notin S$，都有$RMR_u < \theta$的最小种子节点集合$S$。集合$S$的大小称为最优种子节点个数。根据定义我们知道，最优种子节点集合意味着加入新节点后不能再获得理想的影响范围，且预算浪费最小。

\section{实验设置}

有了最优种子个数，一个完整的影响最大化问题应该先给出最优种子节点个数的值，并将该值作为影响最大化算法的输入。然而，给定特定的网络和信息传播模型，应该如何选择最优种子节点个数是从未被研究过的课题。本节拟研究影响最优种子节点个数选择的影响因素，包括网络的规模、网络的结构和信息传播模型的参数等。

我们拟采用对比实验的方法，来找出最优种子节点个数与各个影响因素之间的关系。

\subsection{实验数据集}

在本章中，我们使用两种类型的数据集，一种是模拟生成的网络，另一种是现实网络。对于模拟生成的网络，我们使用ER随机网络以及BA无尺度网络。

ER网络的构造方法很自然，即每对节点之间有边相连的概率都是相同的。假设我们需要生成$n$个节点的ER网络，那么我们只需要以相同的概率$p$加入每条边即可。下图\ref{fig-er-graph}是一个由$n=20$且$p=0.1$生成的ER网络例子。

\begin{figure}[h!]{}
\centering
\includegraphics[width=0.5\textwidth]{figure/chap4/er_20.png}
\caption{ER随机网络示意图}
\label{fig-er-graph}
\end{figure}

BA模型是\cite{barabasi_emergence_1999}中提出的用来解释复杂网络的一个无尺度模型。该模型基于两个假设：
\begin{enumerate}
\item 增长模式：不少现实网络是不断扩大不断增长而来的，例如互联网中新网页的诞生，人际网络中新朋友的加入，新的论文的发表，航空网络中新机场的建造等等。
\item 优先连接模式：新的节点在加入时会倾向于与有更多连接的节点相连，例如新网页一般会有到知名的网络站点的连接，新加入社群的人会想与社群中的知名人士结识，新的论文倾向于引用已被广泛引用的著名文献，新机场会优先考虑建立与大机场之间的航线等等。
\end{enumerate}

根据上述假设，构造一个有$n$个节点的BA网络步骤如下：
\begin{enumerate}
\item 初始时网络有$m_0$（$m_0 \ll n$）个相互连接的节点组成。
\item 每次加入一个新的节点到网络中，新加入的节点被连接到$m < m_0$个已有的节点上，连接的概率与被连接节点和整个网络已有边的个数有关。具体地，新节点被连接到已有节点$i$上的概率为:
$$p_i = \frac{k_i}{\sum_j{k_j}}$$
其中，$k_i$是节点$i$当前的度数，分母是对当前网络中所有节点求和。
\item 重复上面步骤直到节点个数达到$n$。
\end{enumerate}

下图是随机生成的含有20个节点的BA网络的例子。

\begin{figure}[h!]{}
\centering
\includegraphics[width=0.5\textwidth]{figure/chap4/ba_20.png}
\caption{BA无尺度网络示意图}
\label{fig-ba-graph}
\end{figure}

实验中，我们随机生成了节点个数为100万且平均度各不相同的ER网络，以及平均度相同且节点个数各不相同的ER网络。类似地，我们同样随机生成了节点个数为100万且平均度各不相同的BA网络，以及平均度相同且节点个数各不相同的BA网络。为了验证最优种子节点个数在人工生成网络中的规律在现实网络中是否同样适用，我们也使用了两个不同的现实网络。其中一个现实网络是和第四章中相同的微博网络，另一个是与\cite{weng_virality_2013}中相同的推特网络。推特网络和新浪微博网络类似，每个节点代表一个用户，每条边代表用户之间的关注关系，由于关注关系是单向的，因此微博和推特网络都是有向图。现实网络的节点度数分布见图\ref{fig-twitter-weibo}，节点个数及边的个数见表\ref{tab-twitter-weibo-detail}。
\begin{table}
    \centering
    \caption{微博和推特数据细节}
    \label{tab-twitter-weibo-detail}
    \begin{tabular}{lcr}
    \toprule
    数据来源 & 节点个数 & 边的个数 \\
    \midrule 
    推特 & 595460 & 14273311 \\
    微博 & 88532  &  8174703 \\ 
    \bottomrule
    \end{tabular}
\end{table}

\begin{figure}[h!]{}
    \centering
    \begin{tabular}{cc}
        \subfigure[推特网络]{
            \label{fig-twitter-degree-dist}
            \includegraphics[width=.50\textwidth]{figure/chap4/twitter_degree_dist.eps}
        } &
        \subfigure[微博网络]{
            \label{fig-weibo-degree-dist}
            \includegraphics[width=.50\textwidth]{figure/chap4/weibo_degree_dist.eps}
        }
    \end{tabular}
    \caption{推特和微博网络节点分布}
    \label{fig-twitter-weibo}
\end{figure}

\subsection{实验方法与内容}

为了通过实验发现最优种子节点个数与网络规模、网络平均度以及信息传播模型之间的关系，我们设计了如下的实验方法与实验内容：
\begin{enumerate}
\item 使用New Greedy和CI影响最大化算法求出取种子节点集合大小$k=50$时的种子节点集合，并计算每次加入新节点时的影响范围边际收益。

实验中，我们不选取传统的贪心算法和CELF算法，因为这两种算法对于100万规模的网络计算时间太长。而New Greedy算法相对于传统贪心算法，在大大减小算法运行时间的情况下还能保证算法的效果，因此我们选择New Greedy算法来计算种子节点集合。另外，为了说明最优种子节点个数与影响最大化算法无关，我们也使用CI算法进行相同的实验作为对比。由于CI算法和贪心算法的原理不同，它在寻找种子节点集合时，不是通过模拟信息传播过程而是通过计算节点的CI值，因此选择该算法作为对比是较为合适的。
\item 根据最优种子节点个数定义，计算每个网络对应的最优种子节点个数，并研究其与信息传播模型中边传播概率之间的关系。

New Greedy算法在求种子节点集合时，每次加入一个新的节点，都需要模拟信息传播过程。CI算法虽然不需要通过信息传播模型来求种子节点集合，但其在求每个节点影响范围的边际收益时，仍需要通过模拟信息随机传播过程得到。因此，我们需要选择一个信息传播模型来计算每个节点的影响范围。使用效果最好的情绪传播模型是一个自然的选择。然而由于随机生成的网络（ER网络和BA网络）以及推特网络没有信息本身的内容，也没有信息传播的历史轨迹，我们无法估计情绪传播模型中的各个参数，因而无法使用情绪传播模型在该网络中建模。为此我们使用独立传播模型作为基本的信息传播模型。另外，由于没有任何先验知识，我们将所有边的传播概率$p$都设为相同的值。实验中，我们选取了20组不同的$p$作为对比，研究最优种子节点个数与传播概率的关系。
\item 研究最优种子节点个数与网络规模之间的关系。信息在社交网络中传播时，我们的一个直观的感觉是网络规模越大，就需要更多的种子节点将信息传播过去。那么网络规模越大，就需要更大的种子节点集合，需要的最优种子节点个数也越多。为了验证上述直观假设是否正确，我们设置了不同网络规模的对比实验，试图找出最优种子节点个数与网络规模之间的关系。
\item 研究最优种子节点个数与网络平均度之间的关系。

我们知道，网络平均度越大，节点间的边越多，这意味着信息更有机会从一个节点向其他节点传播。一个直观感受是对于相同规模的网络，网络平均度越大，需要的最优种子节点个数越少。为此，本章对于ER网络和BA网络都设置了多组不同平均度的对比实验，拟发现网络平均度对最优种子节点个数的影响。
\item 验证上述实验的结果是否在现实网络中有效。

在前面几条中提到的实验，都是在人工随机生成的ER网络和BA网络中进行的，人工生成的网络不能完全准确地反映现实网络的真实情况。同样，在ER网络和BA网络中的实验结果也不一定完全适用于现实网络。因此，我们使用同样的实验方法在微博和推特网络中进行验证。
\item 验证上述实验的结果对于情绪传播模型是否有效。

之前我们提到，人工随机生成的ER和BA网络以及推特网络缺乏信息及其历史传播轨迹，无法应用于情绪传播模型，因此上述实验都是基于独立传播模型进行的。对于微博数据集，我们在第三章中已经估计出基于该数据集的情绪传播模型参数。因此，本章拟在微博数据集上进行同样实验，研究独立传播模型中最优种子节点个数的性质能否推广得到情绪传播模型。
\end{enumerate}

\subsection{实验结果与分析}

\subsubsection{最优种子节点个数与传播概率}

为了研究最优种子节点个数与信息传播模型中边传播概率之间的关系，我们随机生成规模相同但平均度不同以及平均度相同但规模不同的ER和BA网络，并同时使用NewGreedy算法和CI算法计算最优种子节点个数。最优种子节点个数与信息传播模型中传播概率关系的实验结果如图\ref{fig:optimal_p}所示。子图中的横坐标均为独立传播模型边的传播概率，纵坐标均为其对应的最优种子节点个数，每个子图的名称表示网络的类型。在上面四幅子图中，不同颜色的曲线表示网络不同的平均度，在下面四幅子图中，不同颜色的曲线表示网络不同的规模，网络规模的单位为千。左边四幅子图使用NewGreedy方法计算种子节点集合，右边四幅子图使用CI方法计算种子节点集合。根据定义，求最优种子节点个数需要给定阈值$\theta$，以下实验若无特别说明，均取$\theta=0.01$。

从实验结果中可以看出，最优种子节点个数在边的传播概率很小时首先保持不变，随着传播概率的增加，在一个特定的传播概率下，最优种子节点个数迅速下降，随之达到一个稳定状态。在该稳定状态下，最优种子节点的取值很小。我们称最优种子节点个数迅速下降的现象为相变现象，相变现象结束的点为相变点。

最优种子节点个数关于信息传播模型中传播概率的相变现象表明，在传播概率很小时，网络需要较多的种子节点将信息传播到一个较大范围；而当传播概率很大时，网络只需要较少的种子节点将信息传播到一个较大范围。并且，存在一个突变点$p_c$，使得当传播概率$p<p_c$时，最优种子节点个数取值较大；当$p>p_c$时，最优种子节点个数取值很小。

最优种子节点个数的相变现象意味着当信息传播模型的传播概率达到一定的数值时，影响最大化算法的输入$k$，即种子节点集合的大小可以取一个很小值。这对现实的营销应用很有帮助，例如公司在推广一个产品时，如果发现拟合出的信息传播概率较大，就可以只选取很少量用户免费适用产品，因而可以大大节约预算。

\begin{figure}[h!]{}
  \centering
  \begin{tabular}{cccc}
  \subfigure[ER]{
    \label{fig:optimal_p_a} %% label for first subfigure
    \includegraphics[width=0.4\textwidth]{figure/chap4/ER_newgreedy_stable_p.eps}
  } &
  \subfigure[ER]{
    \label{fig:optimal_p_b} %% label for second subfigure
    \includegraphics[width=0.4\textwidth]{figure/chap4/ER_ci_stable_p.eps}
  } \\
  \subfigure[BA]{
    \label{fig:optimal_p_c} %% label for first subfigure
    \includegraphics[width=0.4\textwidth]{figure/chap4/newgreedy_ba_diffdegree_optimal_p.eps}
  } &
  \subfigure[BA]{
    \label{fig:optimal_p_d} %% label for second subfigure
    \includegraphics[width=0.4\textwidth]{figure/chap4/ci_ba_diffdegree_optimal_p.eps}
  } \\
  \subfigure[ER]{
    \label{fig:optimal_diffN_p_a} %% label for first subfigure
    \includegraphics[width=0.4\textwidth]{figure/chap4/ER_newgreedy_diffN_stable_p.eps}
  } &
  \subfigure[ER]{
    \label{fig:optimal_diffN_p_b} %% label for second subfigure
    \includegraphics[width=0.4\textwidth]{figure/chap4/ER_ci_diffN_stable_p.eps}
  } \\
  \subfigure[BA]{
    \label{fig:optimal_diffN_p_c} %% label for first subfigure
    \includegraphics[width=0.4\textwidth]{figure/chap4/newgreedy_ba_diffn_optimal_p.eps}
  } &
  \subfigure[BA]{
    \label{fig:optimal_diffN_p_d} %% label for second subfigure
    \includegraphics[width=0.4\textwidth]{figure/chap4/ci_ba_diffn_optimal_p.eps}
  } \\
  \end{tabular}
  \caption{最优种子节点个数与传播概率关系图}
  \label{fig:optimal_p} %% label for entire figure
\end{figure}

\subsubsection{相变点与网络}
如果我们知道相变点$p_c$的影响因素或计算方式，那么给定一个网络和信息传播模型，就能判断最优种子节点个数是在相变前还是相变后，从而对最优种子节点个数的选择给出指导。我们知道影响最大化算法的输入除了种子节点个数之外，还有网络和信息传播模型。而给定特定的信息传播模型，输入唯一的不同就是网络本身。一个网络最重要的两个特征是网络规模（即节点个数）和网络平均度。因此我们拟研究相变点与网络规模和网络平均度之间的关系。

为了研究相变点与网络规模和网络平均度之间的关系，我们首先需要计算相变点的位置。在物理中，相变状态为不稳定状态。那么在相变点，每个种子节点的边际收益最不稳定，这意味着每个种子节点边际收益的方差最大。我们基于以上观点，计算不同规模和不同平均度的ER网络和BA网络中最优种子节点个数的相变点。具体地，在使用NewGreedy和CI算法计算得到种子节点以后，需要通过信息传播模型模拟2000次信息随机传播过程来获得每个种子节点的边际收益。由于相变点附近的不稳定性，2000次模拟的节点边际收益结果方差应达到最大。因此，我们计算对于不同的边传播概率，所有种子节点边际收益方差的平均值。方差与独立传播模型中边传播概率的关系实验结果如图\ref{fig:variance_p}所示。图中所有子图横坐标表示独立传播模型中边的传播概率，纵坐标表示种子节点边际收益方差的平均值。上面四幅子图不同曲线表示不同网络平均度，下面四幅子图不同曲线表示不同网络规模。与图\ref{fig:optimal_p}类似，左边四幅子图使用NewGreedy方法计算种子节点集合，右边四幅子图使用CI方法计算种子节点集合。

对比图\ref{fig:optimal_p}和图\ref{fig:variance_p}可以发现，当传播概率较小时，最优种子节点个数比较稳定，对应的种子节点边际收益的方差就比较小；反之，随着传播概率的增加，最优种子节点个数经过一个相变过程，该相变过程对应的种子节点边际收益的方差就很大。当最优种子节点个数达到另一个稳定状态后，对应的种子节点边际收益的方差又降低。因此，种子节点边际收益的方差可以很好地量化最优种子节点个数的相变过程，且方差最大的点即对应相变点。

根据上述基于方差的相变点量化方法，我们计算得到不同规模和不同平均度的ER网络和BA网络中最优种子节点个数的相变点，以及这些相变点对应的边传播概率$p_c$。相变点对应的传播概率$p_c$与网络规模和网络平均度之间的关系如图\ref{fig:pc_graph}所示。图中所有子图的纵坐标均表示相变点对应传播概率$p_c$的取值，在上面四幅子图中，横坐标表示网络的规模，虚线为$y = \frac{1.22}{x}$；在下面四幅子图中，横坐标表示网络的平均度，虚线为$y = \frac{0.3}{x}$。

\begin{figure}[h!]{}
  \centering
  \begin{tabular}{cc}
  \subfigure[ER]{
    \label{fig:variance_p_a} %% label for first subfigure
    \includegraphics[width=0.4\textwidth]{figure/chap4/newgreedy_variance.eps}
  } &
  \subfigure[ER]{
    \label{fig:variance_p_b} %% label for second subfigure
    \includegraphics[width=0.4\textwidth]{figure/chap4/ci_variance.eps}
  } \\
  \subfigure[BA]{
    \label{fig:variance_p_c} %% label for first subfigure
    \includegraphics[width=0.4\textwidth]{figure/chap4/ba_newgreedy_variance_p.eps}
  } &
  \subfigure[BA]{
    \label{fig:variance_p_d} %% label for second subfigure
    \includegraphics[width=0.4\textwidth]{figure/chap4/ba_ci_variance_p.eps}
  } \\
  \subfigure[ER]{
    \label{fig:variance_p_e} %% label for first subfigure
    \includegraphics[width=0.4\textwidth]{figure/chap4/newgreedy_er_diffn_variance_p.eps}
  } &
  \subfigure[ER]{
    \label{fig:variance_p_f} %% label for second subfigure
    \includegraphics[width=0.4\textwidth]{figure/chap4/ci_er_diffn_variance_p.eps}
  } \\
  \subfigure[BA]{
    \label{fig:variance_p_g} %% label for first subfigure
    \includegraphics[width=0.4\textwidth]{figure/chap4/newgreedy_ba_diffn_variance_p.eps}
  } &
  \subfigure[BA]{
    \label{fig:variance_p_h} %% label for second subfigure
    \includegraphics[width=0.4\textwidth]{figure/chap4/ci_ba_diffn_variance_p.eps}
  } \\
  \end{tabular}
  \caption{种子节点边际收益方差与传播概率关系图}
  \label{fig:variance_p} %% label for entire figure
\end{figure}


\begin{figure}[h!]{}
  \centering
  \begin{tabular}{cc}
  \subfigure[ER]{
    \label{fig:pc_graph_a} %% label for first subfigure
    \includegraphics[width=0.4\textwidth]{figure/chap4/newgreedy_er_pc_graphn.eps}
  } &
  \subfigure[ER]{
    \label{fig:pc_graph_b} %% label for second subfigure
    \includegraphics[width=0.4\textwidth]{figure/chap4/ci_er_pc_graphn.eps}
  } \\
  \subfigure[BA]{
    \label{fig:pc_graph_c} %% label for first subfigure
    \includegraphics[width=0.4\textwidth]{figure/chap4/newgreedy_ba_pc_graphn.eps}
  } &
  \subfigure[BA]{
    \label{fig:pc_graph_d} %% label for second subfigure
    \includegraphics[width=0.4\textwidth]{figure/chap4/ci_ba_pc_graphn.eps}
  } \\
  \subfigure[ER]{
    \label{fig:pc_graph_e} %% label for first subfigure
    \includegraphics[width=0.4\textwidth]{figure/chap4/newgreedy_er_pc_degree.eps}
  } &
  \subfigure[ER]{
    \label{fig:pc_graph_f} %% label for second subfigure
    \includegraphics[width=0.4\textwidth]{figure/chap4/ci_er_pc_degree.eps}
  } \\
  \subfigure[BA]{
    \label{fig:pc_graph_g} %% label for first subfigure
    \includegraphics[width=0.4\textwidth]{figure/chap4/newgreedy_ba_pc_degree.eps}
  } &
  \subfigure[BA]{
    \label{fig:pc_graph_h} %% label for second subfigure
    \includegraphics[width=0.4\textwidth]{figure/chap4/ci_ba_pc_degree.eps}
  } \\
  \end{tabular}
  \caption{相变点对应传播概率$p_c$与网络关系图}
  \label{fig:pc_graph} %% label for entire figure
\end{figure}

从实验结果中我们可以看出，相变点对应的边传播概率$p_c$与网络规模无关，而与网络平均度成反比。我们试图从信息传播的过程出发解释这一现象。在第二章我们提到，节点集合在经过独立传播模型的信息传播过程后能激活的节点个数$|RanCas(S)|$满足子模块性和单调性，即随着集合$S$的变大，$|RanCas(S)|$的值增加，且新加入的种子节点可以激活节点个数的边际收益递减。回顾边际收益率的定义$RMR_u=\frac{|RanCas(S^* \cup \{u\}) - RanCas(S^*)|}{|RanCas(S*)|}$，随着集合$S$的增大，式中分母变大，分子变小。因此当种子节点集合达到一定规模后，新加入节点的边际收益率一定会小于阈值$\theta$，即最优种子节点个数一定存在。此外，在相变点处的最优种子个数很小，意味着种子节点集合$S$在很小时，信息的影响范围|RanCas(S)|就已经达到一个较大值，这说明相变点处信息在网络中容易传播，即信息的传播能力强。而在给定信息传播模型下，信息的传播能力由两个因素决定，一个是边的传播概率$p$，另一个是边的密集程度$m$，且信息传播能力正比于$p * m$。网络平均度正是描述一个网络中边密集程度的，因此当网络平均度越大，最优种子节点个数达到相变点所需要的边传播概率就越小；反之，网络的平均度越小，需要的边传播概率就越大。相反地，网络规模与信息的传播能力无关，因此最优种子节点个数的相变点也与网络规模无关。

\subsubsection{相变点与阈值}

在计算最优种子节点个数时，我们需要选择一个阈值$\theta$。之前提到，所有的实验都选择$\theta=0.01$。事实上，只要阈值$\theta$选的足够小，最优种子节点个数的相变位置与阈值的取值无关。区间$(0, 0.01]$中不同的阈值在ER网络和BA网络上的实验结果如下图\ref{fig:diffthd_optimal_p}所示。我们使用平均度为6且规模为100万的ER网络以及平均度为2且规模为100万的BA网络。图中所有子图的纵坐标表示最优种子节点个数，横坐标表示信息模型的传播概率。不同颜色的曲线表示不同的阈值。可以发现在ER网络中，不同阈值下最优种子节点个数与传播概率的关系几乎完全一致；而在BA网络中，虽然开始时最优种子节点个数不同，但是相变点对应的传播概率以及最优种子节点个数完全一致。

\begin{figure}[h!]{}
  \centering
  \begin{tabular}{cc}
  \subfigure[ER]{
    \label{fig:pc_graph_a} %% label for first subfigure
    \includegraphics[width=0.4\textwidth]{figure/chap4/newgreedy_er_diffthd_optimal_p.eps}
  } &
  \subfigure[ER]{
    \label{fig:pc_graph_b} %% label for second subfigure
    \includegraphics[width=0.4\textwidth]{figure/chap4/ci_er_diffthd_optimal_p.eps}
  } \\
  \subfigure[BA]{
    \label{fig:pc_graph_c} %% label for first subfigure
    \includegraphics[width=0.4\textwidth]{figure/chap4/newgreedy_ba_diffthd_optimal_p.eps}
  } &
  \subfigure[BA]{
    \label{fig:pc_graph_d} %% label for second subfigure
    \includegraphics[width=0.4\textwidth]{figure/chap4/ci_ba_diffthd_optimal_p.eps}
  } \\
  \end{tabular}
  \caption{不同阈值最优种子节点个数与传播概率关系图}
  \label{fig:diffthd_optimal_p} %% label for entire figure
\end{figure}

之前提到，我们通过求种子节点边际收益的方差来寻找相变点，而方差的计算与阈值无关。因此在相变点附近，每次模拟信息随机传播过程得到的节点边际收益的不稳定性是客观存在的，并不会随阈值改变而改变。但是如果阈值选择太大，该相变现象不会明显地表现出来。因此在实际应用中，选择一个足够小的阈值即可。

\subsubsection{最优种子个数与网络}

从上面实验我们知道，随着独立传播模型传播概率的增加，最优种子节点个数经历一个相变过程。相变点的传播概率$p_c$与网络规模和阈值$\theta$无关，而网络的平均度近似成反比。在相变点之后，最优种子节点个数达到一个很小的稳定值。该稳定值的大小与网络之间的关系如下图\ref{fig:optimal_network}所示。图中纵坐标均为最优种子节点个数，上面四幅图的横坐标表示网络的平均度，下面四幅图的横坐标表示网络的规模。

\begin{figure}[h!]{}
  \centering
  \begin{tabular}{cc}
  \subfigure[ER]{
    \label{fig:optimal_network_a} %% label for first subfigure
    \includegraphics[width=0.4\textwidth]{figure/chap4/newgreedy_er_optimal_degree.eps}
  } &
  \subfigure[ER]{
    \label{fig:optimal_network_b} %% label for second subfigure
    \includegraphics[width=0.4\textwidth]{figure/chap4/ci_er_optimal_degree.eps}
  } \\
  \subfigure[BA]{
    \label{fig:optimal_network_c} %% label for first subfigure
    \includegraphics[width=0.4\textwidth]{figure/chap4/newgreedy_ba_optimal_degree.eps}
  } &
  \subfigure[BA]{
    \label{fig:optimal_network_d} %% label for second subfigure
    \includegraphics[width=0.4\textwidth]{figure/chap4/ci_ba_optimal_degree.eps}
  } \\
  \subfigure[ER]{
    \label{fig:optimal_network_e} %% label for first subfigure
    \includegraphics[width=0.4\textwidth]{figure/chap4/newgreedy_er_optimal_graphn.eps}
  } &
  \subfigure[ER]{
    \label{fig:optimal_network_f} %% label for second subfigure
    \includegraphics[width=0.4\textwidth]{figure/chap4/ci_er_optimal_graphn.eps}
  } \\
  \subfigure[BA]{
    \label{fig:optimal_network_g} %% label for first subfigure
    \includegraphics[width=0.4\textwidth]{figure/chap4/newgreedy_ba_optimal_graphn.eps}
  } &
  \subfigure[BA]{
    \label{fig:optimal_network_h} %% label for second subfigure
    \includegraphics[width=0.4\textwidth]{figure/chap4/ci_ba_optimal_graphn.eps}
  } \\
  \end{tabular}
  \caption{最优种子个数与网络关系图}
  \label{fig:optimal_network} %% label for entire figure
\end{figure}

从图中可以看出，当达到相变点后，最优种子节点个数与网络的规模和网络的平均度没有对应的数学关系，且最优种子节点个数取值非常小，通常在区间$[2,5]$内。如前面提到的，信息在网络中的传播能力正比于传播概率和网络平均度。随着传播概率的增加，信息在网络中的传播能力增加，当传播能力达到一定数值以后，最优种子节点个数发生相变。而当信息传播能力大到一定数值后，显然很小的种子节点集合就能达到较大的传播范围，因此在相变点之后的最优种子节点个数取值可以很小。然而，我们仅仅根据实验判断最优种子节点个数与网络规模和网络平均度的关系，而没能给出严格的数学推导。因此，如何用数学公式来表示出最优种子节点个数与传播概率和网络平均度的关系，值得进一步研究。

\subsubsection{现实网络与情绪传播模型}

前面提到的实验均是在人工生成的随机网络中得到，为了验证实验的结论是否在现实网络中同样适用，我们使用了微博和推特网络进行实验。其中，推特网络的平均度为47.94，微博网络的平均度为184.67。在实验中，我们分别用NewGreedy方法和CI方法寻找网络的种子节点集合，并基于独立传播模型模拟得到不同传播概率下每个种子节点的边际收益。最后根据最优种子节点集合的定义计算不同网络最优种子节点个数与传播概率的关系。实验结果如下图\ref{fig:real_world}所示，左边两幅子图使用New Greedy方法计算种子节点集合，右边两幅子图使用CI方法计算种子节点集合。

\begin{figure}[h!]{}
  \centering
  \begin{tabular}{cc}
  \subfigure[微博]{
    \label{fig:real_world_a} %% label for first subfigure
    \includegraphics[width=0.4\textwidth]{figure/chap4/newgreedy_weibo_optimal_p.eps}
  } &
  \subfigure[微博]{
    \label{fig:real_world_b} %% label for second subfigure
    \includegraphics[width=0.4\textwidth]{figure/chap4/ci_weibo_optimal_p.eps}
  } \\
  \subfigure[推特]{
    \label{fig:real_world_c} %% label for first subfigure
    \includegraphics[width=0.4\textwidth]{figure/chap4/newgreedy_twitter_optimal_p.eps}
  } &
  \subfigure[推特]{
    \label{fig:real_world_d} %% label for second subfigure
    \includegraphics[width=0.4\textwidth]{figure/chap4/ci_twitter_optimal_p.eps}
  } \\
  \end{tabular}
  \caption{现实网络最优种子节点个数与传播概率关系图}
  \label{fig:real_world} %% label for entire figure
\end{figure}

可以发现，在现实网络包括推特和微博中，最优种子节点个数随着传播概率的增加同样经历一个相变过程。虽然NewGreedy算法和CI算法对于相变的表现不尽相同，但是相变点所在的边传播概率$p_c$非常接近。对于微博网络，NewGreedy方法中的相变位置对应的传播概率为$p_c = 0.003$而CI方法中的相变位置对应的传播概率为$p_c = 0.005$；对于推特网络，NewGreedy方法中的相变位置对应的传播概率为$p_c=0.06$而CI方法中的相变位置对应的传播概率为$p_c=0.05$。忽略NewGreedy方法与CI方法中相变点位置的细微的差异，我们发现微博的网络平均度大而$p_c$小，推特的平均度小而$p_c$大。现实网络的相变位置对应的传播概率$p_c$与网络的平均度同样成反比关系。此外，若传播概率大于相变位置对应的概率$p_c$，微博和推特的最优种子节点个数取值仍满足在区间$[2, 5]$之间。

因此，我们可以推定现实网络仍然满足随机网络中的结论。实际上，无论是微博还是推特，大部分的社交网络都接近于ER或BA网络，因此上述结论可以推广到大多数的社交网络之中。此外，由于在现实社交网络中，每个用户平均的粉丝数和关注数都很大，因此网络大都拥有较大的平均度。而目前的大部分研究通常将独立传播模型的传播概率设为0.01或0.1，对于平均度较大的社交网络，该传播概率远大于相变点对应的概率$p_c$，这表明对于大部分基于独立传播模型的社交影响最大化算法，我们只需要将种子节点个数设置在区间$[2,5]$内即可。

上述关于随机网络和现实网络的结论都是基于独立传播模型的。我们知道独立传播模型对现实社交网络中的信息传播建模能力远不如情绪传播模型，因此接下来的实验拟探寻对于情绪传播模型，基于独立传播模型得出的结论是否同样适用。具体地，我们在微博数据集上使用第三章提到的参数估计方法，求出网络中每条边$(v, u)$关于不同情绪$c$的传播概率$p_{v,u}^c$。同时，我们将微博数据集中每条微博对应情绪的平均值组合为一条信息来代表新浪微博中的典型微博，该微博的情绪组合结果见下表\ref{tab-typical-weibo}。最后，我们使用NewGreedy和CI算法计算在情绪传播模型下，该典型微博在微博网络中的种子节点集合，并通过情绪传播模型模拟得到每个种子节点的边际收益。最后得到最优种子节点个数的结果，两种算法中最优种子节点个数的结果为均为2。

事实上，在确定一条信息的情绪分布$\gamma_i^c$以及估计出每条边对应的情绪传播概率$p_{v,u}^c$以后，就可以计算信息在每条边的传播概率$p_{v,u} = \Sigma_{c}{\gamma_i^c p_{v,u}^c}$。于是在情绪传播模型下，一条确定的信息在网络中的传播过程等同于独立传播模型。实验中，我们计算得到典型微博在网络中传播时，边的平均传播概率为0.1546。而微博网络的平均度为184.67， 根据$p_c$与网络平均度成反比我们知道$p_c$约为0.007。由于情绪传播模型中边的平均传播概率远大于$p_c$，因此我们只需要取种子节点集合个数在区间$[2, 5]$之内即可，而实验结果中最优种子节点个数为2恰好验证了这一点。上述结果初步表明，基于独立传播模型得到的有关最优种子节点个数的结论可以拓展到情绪传播模型中。

\begin{table}
    \centering
    \caption{典型微博的情绪分布}
    \label{tab-typical-weibo}
    \begin{tabular}{cc}
    \toprule
    情绪 & 权重 \\
    \midrule 
    愤怒 & 0.2025 \\
    厌恶 & 0.1064 \\
    高兴 & 0.4270 \\
    低落 & 0.1975 \\
    恐惧 & 0.0646 \\
    \bottomrule
    \end{tabular}
\end{table}

\section{本章小结}

现有研究中的大多数影响最大化算法的研究致力于发现更准确的种子节点集合或提高计算种子节点集合的效率使其适用于大规模的网络。和这些工作不同，本章研究如何选择种子节点集合大小才能使得在影响范围足够大的同时节约预算。本章称满足这种情况的种子节点集合大小为最优种子个数。

本章首先给出了最优种子个数的形式化定义以及计算方法。其次，本章通过设计一系列在人工生成的ER和BA随机网络以及现实网络的实验，得出以下结论：
\begin{enumerate}
\item 随着独立传播模型传播概率的增加，最优种子节点个数经过相变并迅速下降到一个很小值，且该值通常在区间$[2,5]$中。
\item 最优种子节点个数相变点对应的信息传播概率与网络规模和阈值$\theta$无关，而与网络的平均度成反比。
\item 在信息传播模型的传播概率达到相变点之后，最优种子节点个数的取值与网络规模和网络平均度均无关。
\item 现实社交网络包括微博和推特同样满足上述三条结论。
\end{enumerate}

最后，本章通过在微博数据集上的情绪传播模型实验，发现上述结论同样适用情绪传播模型。